In a stochastic computer, values are represented as a stream of outcomes of a Bernoulli process. In such a computer, each value is represented by the probability of a particular state in the Bernoulli process. For example, a value of “0.7” would be represented by a stream of outcomes in which the probability that a particular outcome is in a first state is 0.7 and the probability that a particular outcome is in a second state is 0.3.
Accordingly, in a stochastic computer, one can estimate the value that is being represented by observing the outcome stream that represents that value. The longer one observes the outcome stream, the more accurate the estimate will be.
The use of outcome streams to represent values offers numerous advantages. For example, to multiply two numbers, a conventional computer would need to carry out a fairly complex procedure. In contrast, to multiply the same two numbers in a stochastic computer, one need only use an “AND” gate to “and” together corresponding bits in the two outcome streams as they arrive.
In a typical stochastic computer, the outcomes of the Bernoulli process are generated by a random number generator. A difficulty that arises, however, is that the numbers generated by a practical random number generator are only pseudo-random. These pseudo-random numbers are random enough for many purposes. However, the lack of true randomness becomes apparent when such random number generators are used in stochastic computers.
For example, since the random number generators can only generate pseudo-random numbers, the string of random numbers will eventually repeat itself. This repetition can cause errors in calculations that rely on the randomness of two incoming outcome streams. In other cases, there may be correlation between what are intended to be two independent outcome streams.
To overcome such difficulties, many stochastic computers use additional random number generators to re-randomize incoming outcome streams. These re-randomizers are analogous to repeaters in communication circuits, except that while repeaters are intended to boost a signal to avoid having it be lost in noise, the re-randomizers are intended to boost the noise to drown out any unwanted signal.
A difficulty that arises with the proliferation of re-randomizers is that each one consumes both additional power and additional floor-space. In a stochastic computer in which messages are being passed simultaneously between hundreds, and possibly thousands of node pairs, the additional power and floor-space required by these re-randomizers becomes considerable.